{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a19f89e9-21fc-4399-898b-b79f77de8c3a",
   "metadata": {},
   "source": [
    "# Grover Operator\n",
    "\n",
    "The Grover operator is a unitary used in amplitude estimation and amplitude\n",
    "amplification algorithms [[1]](#1). The Grover operator is given by\n",
    "\n",
    "$$\n",
    "Q = Q(A,\\chi) = -AS_0A^{-1}S_\\chi\n",
    "$$\n",
    "\n",
    "where $A$ is a state preparation operator,\n",
    "\n",
    "$$\n",
    "A|0 \\rangle= |\\psi \\rangle\n",
    "$$\n",
    "\n",
    "$S_\\chi$ marks good states and is called an oracle,\n",
    "$$\n",
    "S_\\chi\\lvert x \\rangle = \n",
    "\\begin{cases} \n",
    "-\\lvert x \\rangle & \\text{if } \\chi(x) = 1 \\\\\n",
    " \\phantom{-} \\lvert x \\rangle & \\text{if } \\chi(x) = 0 \n",
    "\\end{cases}\n",
    "$$\n",
    "and $S_0$ is a reflection about the zero state. \n",
    "\n",
    "$$\n",
    "S_0 = I - 2|0\\rangle\\langle0|\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2e4a2a3-c2f9-4d10-8656-dfd92048ed93",
   "metadata": {},
   "source": [
    "Function: `grover_operator`\n",
    "\n",
    "Arguments:\n",
    "\n",
    "- `oracle: QCallable[QArray[QBit]]` - Oracle representing $S_{\\chi}$, accepting quantum state to apply on.\n",
    "- `space_transform: QCallable[QArray[QBit]]` - State preparation operator $A$, accepting quantum state to apply on.\n",
    "- `packed_vars: QArray[QBit]` - Packed form of the variable to apply the grover operator on."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d7c22bd-f0d5-460e-8611-0930996c5a36",
   "metadata": {},
   "source": [
    "### Example\n",
    "\n",
    "The following example implements a grover search algorithm using the grover operator for a specific oracle, with a uniform superposition over the search space.\n",
    "The circuit starts with a uniform superposition on the search space, followed by 2 applications of the grover operator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "10f00ffb-e800-4d38-8558-186320e92d99",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:24:56.268922Z",
     "iopub.status.busy": "2024-05-07T13:24:56.266205Z",
     "iopub.status.idle": "2024-05-07T13:24:59.146024Z",
     "shell.execute_reply": "2024-05-07T13:24:59.145179Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import (\n",
    "    Constraints,\n",
    "    Output,\n",
    "    QArray,\n",
    "    QBit,\n",
    "    QCallable,\n",
    "    QNum,\n",
    "    allocate,\n",
    "    bind,\n",
    "    create_model,\n",
    "    grover_operator,\n",
    "    hadamard_transform,\n",
    "    phase_oracle,\n",
    "    power,\n",
    "    qfunc,\n",
    ")\n",
    "from classiq.qmod.symbolic import logical_and\n",
    "\n",
    "VAR_SIZE = 2\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def my_predicate(x: QNum, y: QNum, res: QBit) -> None:\n",
    "    res ^= logical_and((x + y < 9), ((x * y) % 4 == 1))\n",
    "\n",
    "\n",
    "@qfunc\n",
    "def main(x: Output[QNum[VAR_SIZE, False, 0]], y: Output[QNum[VAR_SIZE, False, 0]]):\n",
    "    packed_vars = QArray(\"packed_vars\")\n",
    "    allocate(2 * VAR_SIZE, packed_vars)\n",
    "\n",
    "    hadamard_transform(packed_vars)\n",
    "\n",
    "    power(\n",
    "        2,\n",
    "        lambda: grover_operator(\n",
    "            lambda vars: phase_oracle(\n",
    "                predicate=lambda _vars, _res: my_predicate(\n",
    "                    _vars[0:VAR_SIZE], _vars[VAR_SIZE : _vars.len], _res\n",
    "                ),\n",
    "                target=vars,\n",
    "            ),\n",
    "            lambda vars: hadamard_transform(vars),\n",
    "            packed_vars,\n",
    "        ),\n",
    "    )\n",
    "    bind(packed_vars, [x, y])\n",
    "\n",
    "\n",
    "constraints = Constraints(max_width=15)\n",
    "qmod_grover = create_model(main, constraints=constraints)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1be60ce8-8039-46ed-9823-e531efdc47c3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:24:59.152464Z",
     "iopub.status.busy": "2024-05-07T13:24:59.151666Z",
     "iopub.status.idle": "2024-05-07T13:25:03.890219Z",
     "shell.execute_reply": "2024-05-07T13:25:03.889188Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import synthesize, write_qmod\n",
    "\n",
    "write_qmod(qmod_grover, \"grover_operator\")\n",
    "qprog = synthesize(qmod_grover)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7ccbdd9-101b-4014-87f0-4292966d6203",
   "metadata": {},
   "source": [
    "And the next is a verification of the amplification of the solutions to the oracle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2ab73502-297e-4f4f-a1c7-39e1b269c823",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:25:03.894152Z",
     "iopub.status.busy": "2024-05-07T13:25:03.893696Z",
     "iopub.status.idle": "2024-05-07T13:25:06.499374Z",
     "shell.execute_reply": "2024-05-07T13:25:06.498645Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'x': 3.0, 'y': 3.0}: 479,\n",
       " {'x': 1.0, 'y': 1.0}: 473,\n",
       " {'x': 1.0, 'y': 0.0}: 5,\n",
       " {'x': 1.0, 'y': 3.0}: 5,\n",
       " {'x': 2.0, 'y': 1.0}: 5,\n",
       " {'x': 3.0, 'y': 2.0}: 5,\n",
       " {'x': 2.0, 'y': 0.0}: 4,\n",
       " {'x': 0.0, 'y': 2.0}: 4,\n",
       " {'x': 3.0, 'y': 1.0}: 4,\n",
       " {'x': 0.0, 'y': 0.0}: 4,\n",
       " {'x': 0.0, 'y': 3.0}: 3,\n",
       " {'x': 1.0, 'y': 2.0}: 3,\n",
       " {'x': 2.0, 'y': 3.0}: 2,\n",
       " {'x': 0.0, 'y': 1.0}: 2,\n",
       " {'x': 2.0, 'y': 2.0}: 1,\n",
       " {'x': 3.0, 'y': 0.0}: 1]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from classiq import execute\n",
    "\n",
    "res = execute(qprog).result()[0].value\n",
    "res.parsed_counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a63180c7-f2b3-444e-a518-e9bb3f3f1298",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:25:06.503296Z",
     "iopub.status.busy": "2024-05-07T13:25:06.502847Z",
     "iopub.status.idle": "2024-05-07T13:25:06.510679Z",
     "shell.execute_reply": "2024-05-07T13:25:06.510102Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 False\n",
      "0 1 False\n",
      "0 2 False\n",
      "0 3 False\n",
      "1 0 False\n",
      "1 1 True\n",
      "1 2 False\n",
      "1 3 False\n",
      "2 0 False\n",
      "2 1 False\n",
      "2 2 False\n",
      "2 3 False\n",
      "3 0 False\n",
      "3 1 False\n",
      "3 2 False\n",
      "3 3 True\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "\n",
    "for x, y in product(range(2**VAR_SIZE), range(2**VAR_SIZE)):\n",
    "    print(x, y, (x + y < 9) and ((x * y) % 4 == 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00f8feca-6f2a-444e-973e-20be5dc9bed0",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "<a name=\"1\">[1]</a> G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, \u201cQuantum\n",
    "Amplitude Amplification and Estimation,\u201d arXiv:quant-ph/0005055, vol. 305, pp.\n",
    "53\u201374, 2002, doi: 10.1090/conm/305/05215."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
